//Given a string s, partition s such that every substring of the partition is a 
//palindrome. Return all possible palindrome partitioning of s. 
//
// A palindrome string is a string that reads the same backward as forward. 
//
// 
// Example 1: 
// Input: s = "aab"
//Output: [["a","a","b"],["aa","b"]]
// Example 2: 
// Input: s = "a"
//Output: [["a"]]
// 
// 
// Constraints: 
//
// 
// 1 <= s.length <= 16 
// s contains only lowercase English letters. 
// 
// Related Topics 深度优先搜索 动态规划 回溯算法 
// 👍 757 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//Java：Palindrome Partitioning
 class P131PalindromePartitioning{
    public static void main(String[] args) {
        Solution solution = new P131PalindromePartitioning().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        boolean[][] visited;
        List<List<String>> result = new ArrayList<>();
        List<String> ans = new ArrayList<>();
        int n;
        public List<List<String>> partition(String s) {
            n = s.length();
            visited = new boolean[n][n];
            for (int i = 0; i < n; ++i) {
                Arrays.fill(visited[i], true);
            }

            for (int i = n - 1; i >= 0; --i) {
                for (int j = i + 1; j < n; ++j) {
                    visited[i][j] = (s.charAt(i) == s.charAt(j)) && visited[i + 1][j - 1];
                }
            }

            dfs(s, 0);
            return result;
        }

        public void dfs(String s, int i) {
            if (i == n) {
                result.add(new ArrayList<String>(ans));
                return;
            }
            for (int j = i; j < n; ++j) {
                if (visited[i][j]) {
                    ans.add(s.substring(i, j + 1));
                    dfs(s, j + 1);
                    ans.remove(ans.size() - 1);
                }
            }
        }

        public List<List<String>> partitionII(String s) {
            n = s.length();
            visited = new boolean[n][n];
            dfsII(s, 0);
            return result;
        }

        private void dfsII(String s, int i) {
            if (i == n) {
                result.add(new ArrayList<>(ans));
                return;
            }
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j)) {
                    ans.add(s.substring(i, j + 1));
                    dfsII(s, j + 1);
                    ans.remove(ans.size() - 1);
                }
            }
        }

        public boolean isPalindrome(String s, int i, int j) {
            if (visited[i][j] == true) {
                return visited[i][j];
            }
            if (i >= j) {
                visited[i][j] = true;
            } else if (s.charAt(i) == s.charAt(j)) {
                visited[i][j] = isPalindrome(s, i + 1, j - 1);
            } else {
                visited[i][j] = false;
            }
            return visited[i][j];
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}